package com.zk.algorithm.greedy;

import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.TiaoZhanChengXuSheJiJingSai;
import com.zk.algorithm.bean.Interval;

import java.util.Arrays;
import java.util.Comparator;

/**
 * si -> ti
 *
 * 每次选取结束时间最早的工作
 *
 * @author zk
 */
@TiaoZhanChengXuSheJiJingSai("区间调度问题")
public class WatchTV {

    public static void main(String...args) {
        Utils.println(new WatchTV().mostWatchNums(new Interval[]{
                new Interval(1, 3),
                new Interval(2, 5),
                new Interval(4, 7),
                new Interval(6, 9),
                new Interval(8, 10)
        }));
    }

    public int mostWatchNums(Interval[] intervals) {
        sort(intervals);
        return doFindMostWatchNums(intervals);
    }

    public int doFindMostWatchNums(Interval[] intervals) {
        int ans = 0;
        int lastEnd = 0; // 最后所选工作的结束时间

        for (int i = 0; i < intervals.length; i++) {
            if (intervals[i].start > lastEnd) {
                ans++;
                lastEnd = intervals[i].end;
            }
        }

        return ans;
    }

    public void sort(Interval[] intervals) {
        Arrays.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if (o1.end < o2.end) {
                    return -1;
                } else if (o1.end > o2.end) {
                    return 1;
                }

                return 0;
            }
        });
    }

}